Para este filtro hemos probado con dos implementaciones. La anterior, que presentamos en la primer fecha, era te\'oricamente correcta pero ineficiente en cuesti\'on de performance.

Como en este trabajo practico se busca conocer las herramientas, provistas por el micropocesador y el lenguaje de bajo nivel, para la comprensi\'on y mejora de la performance, 
hemos optado por rehacer la implementaci\'on del mismo. A continuaci\'on se presenta la descripcion de la implementaci\'on actual.


\subsection{Descripci\'on}

Este filtro toma un rect\'angulo de la imagen original y lo devuelve en una nueva imagen, invertido horizontalmente, como se muestra a continuaci\'on.

\begin{figure}[H]
    \begin{center}
    \includegraphics[width=75mm,scale=1]{cropflipEfecto.png}
    \caption{Esquema explicativo de efecto: Cropflip.}
    \end{center}
  \label{cropflip13c}
\end{figure}
 
El rectangulo se considerar\'a a partir de la columna \verb|offset_x|, fila \verb|offset_y|, con dimensi\'on \verb|tamx*tamy|, como se muestra en la figura 2.

\begin{figure}[H]
    \begin{center}
    \includegraphics[width=120mm,scale=1]{cropflipParametros.png}
    \caption{Esquema explicativo del uso de par\'ametros: Cropflip.}
    \end{center}
  \label{cropflip13c}
\end{figure}
 

 La descripci\'{o}n formal de este filtro est\'a caracterizada por la siguiente f\'{o}rmula:
\begin{equation*}
 dst(i,j) = src(tamy+offsety-i-1,offsetx+j)
\end{equation*}

Describi\'endolo de manera concisa, el algoritmo implementado es el siguiente:

\begin{codesnippet}
\begin{verbatim}
        sea s un puntero al principio de la zona indicada en la imagen fuente
        sea d un puntero al principio de la ultima fila de la imagen destino
        mientras s permanezca en la zona indicada
                leer 4 pixeles a partir de s
                grabar esos 4 pixeles a partir de f
                si s no llego al final de la fila
                        s = s + 16
                        f = f + 16
                sino
                        posicionar s al principio de la fila de abajo
                        posisionar f al principio de fila de arriba
		
\end{verbatim}
\end{codesnippet}donde la zona indicada est\'a determinada por los valores tamx, tamy, offset\_x y offset\_y.\\

Para operar con las im\'agenes, contamos con los punteros $src$ y $dst$, que apuntan al primer p\'ixel de las im\'agenes fuente y destino, respectivamente.
Por lo tanto, para trabajar en la zona indicada debemos, en primer lugar, avanzar el puntero $src$ al primer
p\'ixel de la misma: lograremos esto incrementando el puntero $src$ al valor \verb|src + (offsety * src_row_size) + offsetx|.

Teniendo esto, vamos a recorrer la imagen destino en orden reverso
respecto de las filas; es decir, recorreremos las filas de la imagen destino de abajo hacia arriba. Como la orientaci\'on horizontal debe preservarse, recorreremos
cada fila de la imagen destino de la misma manera que las filas de la imagen fuente: de izquierda a derecha, manteni\'endonos dentro del area indicada 
en la imagen fuente, incrementando el puntero de la imagen fuente \verb|src_row_size-tamx-offsetx|bytes y, an\'alogamente, decrementando el puntero sobre la imagen 
destino en \verb|dst_row_size-tamx| bytes.
Dentro de este ciclo nos limitamos a copiar la informacion entre im\'agenes, sin ning\'un tipo de procesamiento, de a 4 p\'ixeles, pues nos limita el tama\~no de 
los registros XMM.

%si el parrafo anterior tuviese una erre mas, lo declararia trabalenguas!!!

Para evitar el padding, cada vez que nos posicionamos sobre una nueva fila, guardamos un puntero p al principio de la misma, De este modo, cuando 
llegamos al final de la fila, nos limitamos a avanzar a la siguiente sum\'andole al puntero p el valor \verb|src_row_size|. Lo mismo aplica para los dem\'as filtros.
 
\subsection{Experimentaci\'on}

\subsubsection{An\'alisis del c\'odigo generado}

En este experimento analizaremos el c\'{o}digo generado por la herramienta objdump aplicada sobre el archivo cropflip$\textunderscore$c.o, tomando como
gu\'{i}a las preguntas formuladas por la c\'{a}tedra en el enunciado.

En cuanto a la existencia de otras funciones aparte de cropflip$\textunderscore$c, nuestra impresi\'{o}n inicial indicaba que muchas de las otras funciones 
aparecen en el c\'{o}digo ensamblado con el objetivo de proveer informaci\'{o}n \'{u}til para debuggear el programa encargado de aplicar el filtro. Se nos
ocurri\'{o} que esto era as\'{i}, principalmente, por los nombres de las funciones generadas: debug$\textunderscore$info, debug$\textunderscore$abbrev y 
debug$\textunderscore$loc son algunos ejemplos. Pudimos corroborar esto removiendo el flag -ggdb del Makefile, compilando 
y generando el c\'{o}digo ensamblado nuevamente, pues las funciones mencionadas anteriormente ya no estaban en dicho c\'{o}digo.

En cuanto a la manipulaci\'{o}n de las variables, observamos en el c\'{o}digo generado que las variables locales est\'{a}n definidas en el stack, con lo cual
un acceso a cualquiera de ellas, ya sea lectura o escritura, significa un acceso a memoria. Mencionamos como optimizaci\'{o}n posible el uso de registros de 
prop\'{o}sito general para el almacenamiento de las variables locales, en lugar de la pila, pues acceder a dichos registros es m\'{a}s 
r\'{a}pido que un acceso a la memoria.

%insertando conclucion estupida y obvia en 3... 2... 1... 

Durante el an\'alisis del c\'odigo generado, concluimos que el flag -O0, con el cual compilamos, no realiza optimizacion alguna. Es decir, el c\'odigo obtenido, 
excluyendo las funciones para debug, es practicamente una traducci\'on directa del algoritmo escrito en lenguaje C. 

%momento, esto no es una conclusion, es algo que pablo me conto que pasaba, despues de que lo leyo en internet. Bueno, como me lo conto un integrante del grupo,
%cuenta como un debate al respecto. XD

\subsubsection{Optimizaciones del compilador}

En este experimento haremos un an\'{a}lisis an\'{a}logo al del punto anterior, pero compilando el c\'{o}digo de C con el flag -O1.

En primer lugar, observamos que el c\'{o}digo de la funci\'{o}n \verb|cropflip_c| empieza con pushes de algunos registros de prop\'{o}sito general
(\verb|R12|, \verb|R13|), para luego usarlos como variables en dicha funci\'{o}n, lo cual ayuda a reducir la cantidad de instrucciones donde se direccione a memoria.
Para ver qu\'{e} flags brinda el compilador para optimizar el c\'{o}digo, ejecutamos en la terminal \verb|man gcc| y a modo de ejemplo, mencionaremos 3 de ellos:
\verb|-O1|, \verb|-Ofast|, \verb|-Os|. Por \'{u}ltimo, comentaremos brevemente 3 optimizaciones que hace el gcc sobre el c\'{o}digo, al compilar
con el flag de optimizaci\'on \verb|-O1|: 

\verb|-falign-functions=n|, que alinea el comienzo de las funciones a direcciones multiplos de $n$, siendo $n$ una potencia de 2.

\verb|-falign-loops=n|, que hace una optimizaci\'on an\'aloga a la anterior pero sobre los loops que haya dentro del c\'odigo.

\verb|-funroll-all-loops| (en espa\~nol: desenrollar todos los bucles), que intenta reducir el tiempo de ejecuci\'on de los bucles dentro de un 
programa mediante la reescritura de las operaciones ejecutadas dentro de un ciclo como instrucciones independientes (en la medida en que esto sea
posible), pues esto permitir\'ia ejecutarlas en paralelo en lugar de hacerlo secuencialmente.

\subsubsection{Calidad de la mediciones}

Para llevar a cabo este experimento decidimos que, al tener como objetivo comprobar la calidad de las mediciones tomadas cuando se aplica el filtro,
deb\'iamos considerar, en todos los incisos, la misma imagen de prueba con identicos parametros en todas las 
mediciones. Esto es para poder mostrar en detalle c\'omo var\'ian el tiempo de ejecuci\'on, la media y la varianza, cuando var\'ian solamente los recaudos num\'ericos 
tomados sobre las observaciones, ya sea descartar o no los outliers, o tomar en cuenta que hay programas corriendo en simult\'aneo con la ejecuci\'on del filtro.
Con esto en mente, usamos como caso de prueba para este ejercicio la imagen \verb|lena.1024x767.png|, y 
los siguientes valores para los par\'ametros espec\'ificos de este filtro: $tamx = 1000$, $tamy = 600$, $offsetx = 16$ y $offsety = 15$.

Tomamos esta decisi\'on bas\'andonos en c\'omo creemos$^1$ que funciona el scheduler del sistema operativo. Es decir, si recorre circularmente las tareas activas, 
asign\'andole a cada una cantidad de tiempo,
pod\'{i}a darse el caso en que el programa encargado de aplicar el filtro terminara en la ``primera vuelta'', con lo cual el efecto del loop infinito corriendo
de fondo podr\'ia no apreciarse. Con esto nos referimos a que
la aplicacion del filtro necesitara menos tiempo que el quantum que le fue asignado, comportamiento que se torna mas probable si la imagen destino es peque\~na,
lo que supondria que no se produzca un intercambio de tareas dentro de la medici\'on.


\begin{figure}[H]
    \begin{center}
    \includegraphics[width=0.5\textwidth]{cropflip13nueva}
    \end{center}
  \label{cropflip13c}
\end{figure}

En el gr\'{a}fico podemos observar que, en promedio, el procesador tarda m\'{a}s ciclos de clock en aplicar el filtro cuando los 
cores l\'{o}gicos est\'{a}n ocupados con el loop infinito. Esto se corresponde con el comportamiento esperado, pues al aplicar el filtro con los loops de fondo, 
el uso de los procesadores debe dividirse entre estos procesos.

Ademas podemos ver en el gr\'{a}fico que al descartar los outliers, disminuye la varianza en las
mediciones. Esto tambi\'{e}n es esperable, porque, como el procesador debe alternar las ejecuciones de los distintos procesos en funcionamiento, es razonable esperar
que haya un margen de error, no despreciable, en las mediciones. Descartando una cantidad $k$ de las mediciones m\'as extremas pretendemos que los valores
restantes se encuentren m\'as cerca de la media, causando as\'i una disminuci\'on en la varianza.

Por otro lado, observamos una leve disminuci\'{o}n en la media calculada despu\'{e}s del descarte. Concluimos que, si bien no es cierto que
esto ocurra para cualquier medici\'{o}n de cualquier fen\'{o}meno, en este caso es natural que no haya
valores an\'{o}malos que est\'{e}n muy por debajo de la media, pues la cantidad de ciclos de clock que le lleva al procesador aplicar el filtro
puede acotarse inferiormente, acotando por la cantidad de p\'{i}xeles en la imagen destino, por ejemplo. Esto implica que todas las mediciones deber\'{i}an estar
por encima de dicha cota, pero s\'{i} se pueden presentar mediciones muy por encima de la media, ya que el scheduler podr\'{i}a saltar a otra tarea
antes de terminar de aplicar el filtro y pasar por varias mas antes de volver a ejecutar el filtro.

\footnotetext[1]{ Nos basamos en nuestra intuci\'on, creyendo de buena fe en que los programadores del sistema operativo trabajaban con un m\'inimo de l\'ogica, para formular 
esta hip\'otesis. Nos debimos conformar con esta hip\'otesis pues no contabamos con tiempo suficiente, entre un mes y un par de a\~nos, para \emph{intentar}
comprender la funci\'on \emph{sched()} del linux sobre el que operamos.}

\subsubsection{Secuencial vs. Vectorial}

En este experimento queremos comprobar emp\'{i}ricamente la utilidad de programar en un lenguaje de bajo nivel. Es decir, queremos comprobar si,
para este tipo de programa, logramos una performance mejor a aquellas obtenidas de optimizaciones de c\'{o}digo en lenguaje C. Al escribir ``este tipo de programa''
nos referimos a los programas que pueden ser categorizados como semejantes al filtro Cropflip. Los cuales, seg\'un nuestro criterio, serian aquellos 
que se limitan a transferir informaci\'on sin modificarla.

Para este experimento, decidimos tomar rect\'angulos,  delimitados por las variables \verb|tamx| y \verb|tamy|, que fueran creciendo en tama\~no 
proporcionalmente a las dimensiones de las im\'agenes sobre las cuales hicimos los experimentos. Aproximadamente, 4/5 de cada imagen.
Adem\'as, dejamos fijos los par\'ametros \verb|offsetx| y \verb|offsety| en los valores 16 y 15, ya que el valor de estos par\'ametros
no modifica el tiempo asint\'otico de ejecuci\'on del filtro. Esto es porque \verb|offsetx| y \verb|offsety| no determinan m\'as la cantidad de bytes que  
debe desplazarse el puntero sobre la imagen fuente antes de entrar al ciclo de procesamiento.

En este gr\'{a}fico, mostramos las diferencias de performance entre las versiones de cropflip en Assembler y distintas optimizaciones de la versi\'{o}n de
C. Notar\'a el lector que hemos dejado afuera de este gr\'{a}fico la versi\'{o}n en C compilada con el flag de optimizaci\'on -O0. Decidimos hacer esto
porque la performance de dicha versi\'on era mucho peor que todas las otras versiones del filtro, con lo cual no pod\'ian apreciarse las diferencias de 
menor orden de magnitud que hay entre las otras versiones. 
 


\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip14nueva}
  \label{cropflip14}
\end{figure}
 
Podemos observar en el gr\'afico que esta implementaci\'on de cropflip obtiene en promedio, a diferencia de la anterior,
una mejor performance que todas las optimizaciones sobre la versi\'on en C. Tambien se observan las mejoras esperadas al compilar con los sucesivos flags de 
optimizaci\'on.

%%conclucion inutil y obvia, yo te elijo!

A partir del an\'alisis de los resultados obtenidos, no solo en este sino en todos los experimentos de este tipo realizados para los distintos filtros, concluimos
que, si se optimiza correctamente, la transferencia de datos se puede mejorar significativamente con respecto al resultado provisto por el compilador. Esto 
contradice la conclusi\'on a la que llegamos en la primer instancia, lo cual resalta el hecho de que si no optimizamos el algoritmo para aprovechar al m\'aximo las 
herramientas disponibles obtendremos una perfomance pobre, a\'un si lo implementamos en lenguaje de bajo nivel.


 
\subsubsection{CPU vs. Bus de memoria}

En este experimento intentamos determinar cu\'{a}l es el factor limitante para la performance del filtro. Por lo tanto, tomamos mediciones para las mismas 
im\'{a}genes agregando distintos tipos de instruciones de operaciones aritm\'{e}ticas y accesos a memoria para lograr una variaci\'{o}n en la performance que
nos permita decidir qu\'{e} tipo de instrucciones es el que influye de mayor manera en el tiempo de ejecuci\'{o}n.

Para este experimento, decidimos hacer todas las mediciones sobre la misma imagen. Tomamos esta decisi\'on porque, si deb\'iamos decidir qu\'e tipo
de operaci\'on es m\'as costosa para el procesador, obtendr\'iamos conclusiones id\'enticas experimentando
sobre todas las im\'agenes disponibles. La imagen elegida fue \verb|lena.512x512.bmp|. Las instrucciones agregadas fueron:
\verb|add rax, rbx| para las aritm\'eticas, y \verb|mov rax, [rsp]| y \verb|mov [rsp+8],rax| para las de transferencia de datos,
ambas sugeridas por la c\'atedra.


\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip15nueva}
  \label{cropflip14}
\end{figure}

Adicionalmente, y por requerimiento del enunciado, mostramos en forma de tabla los valores correspondientes al gr\'afico anterior:

\begin{center}
   \begin{tabular}{| c | c | c | c | r | c | r | c | r |c | r |c | r |}
     \hline
     Versi\'on del filtro en assembler & Media & Varianza  \\ \hline
     Original& 735857.67 & 21.20 \\ \hline
     Con 4 aritm\'eticas extra & 794771.16 & 35.47 \\ \hline
     Con 8 aritm\'eticas extra & 873790.16 & 37.19  \\ \hline
     Con 16 aritm\'eticas extra & 1054161.5 & 98.51 \\ \hline
     Con 4 accesos a memoria extra & 867239.16 & 30.54 \\ \hline
     Con 8 accesos a memoria extra & 1224430.67 & 219.56 \\ \hline
     Con 16 accesos a memoria extra & 2376139.67 & 5945.99 \\ \hline
   \end{tabular}
\end{center}

En este gr\'afico, podemos observar, en primer lugar, que no resulta indiferente el agregado de ninguno de los dos tipos de instrucciones; m\'as a\'un, 
el impacto en la performance es significativo para ambos casos. Luego de analizar los resultados, deteminamos que el limitante de performance en este caso
son los accesos a memoria ya que, para las 3 cantidades de instrucciones extra, el tiempo resulta mayor para la versi\'on
con m\'as accesos a memoria. Esto nos da la nocion intuitiva de que un acceso a memoria es mas lento que la ejecucion de una instruccion 
aritmetica en general.
